package Data_Structure.List.MyList;

import java.util.ArrayList;

/**
 * @className: Test1
 * @author: 芃
 * @description: 链表OJ题目练习
 * @date: 2023/8/16 18:40
 */
public class Test1 {
    public static void main(String[] args) {

    }
    //环形链表2-》判断链表是否有环，有则返回入环的节点，否则返回null
    //思路和判断链表成环类似，区别在于相遇时返回fast即可
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;//只有一个节点或空节点则不构成环形
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                //说明相遇了,循环结束
                break;
            }
        }
        if (fast == null || fast.next == null){
            //说明没相遇，且fast把链表走到了头
            return null;
        }else {
            //※※※结论：相遇之后，一个从相遇点开始，一个从头开始，一人一步走，最后相遇的地方就是入口点
            fast = head;
            while (fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    //判断链表是否有环
    //思路：快慢指针，快的走2步，慢的走1步，如果成环，快慢指针终会相遇
    //什么情况下不构成环？当快的走到null了还没有相遇，此时就说明无环
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;//只有一个节点或空节点则不构成环形
        }
        ListNode fast = head.next.next;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            if (fast != slow){
                fast = fast.next.next;
                slow = slow.next;
            }else {
                //说明相遇了
                return true;
            }
        }
        //能走到这，说明没相遇，且fast把链表走到了头
        return false;
    }

    //求两个链表的第一个公共节点-值一样且next域也一样
    //思路1：hashSet，将A链表的节点存储到Set，再去链表B遍历，看看Set里面包不包含这个节点，包含则返回
    //思路2：双指针
    //求两个链表的长度，让长的链表先走差值步
    //长链表走完差值步后和另外一个链表同步走
    //相交时就返回相交时的节点，否则就返回null
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int size1 = getSize(headA);
        int size2 = getSize(headB);
        int sub = Math.abs(size1 - size2);//求差值的绝对值
        ListNode p1 = headA;
        ListNode p2 = headB;
        if (size1 > size2){
            for (int i = 0; i < sub; i++) {
                p1 = p1.next;
            }
        }else {
            for (int i = 0; i < sub; i++) {
                p2 = p2.next;
            }
        }
        //求相遇交点
        while (p1 != null){
            if (p1 == p2){
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
    //求链表长度
    public int getSize(ListNode head){
        int count = 0;
        while (head != null){
            head = head.next;
            count++;
        }
        return count;
    }

    //删除链表中重复的节点
    public ListNode deleteDuplication(ListNode pHead) {
        //使用虚拟节点，不重复的元素都挂到虚拟节点的后面
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = pHead;
        while (cur != null){
            if (cur.next != null && cur.val == cur.next.val){
                while (cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                //走到这，说明重复的走到最后一个重复的了，此时再让cur向后走
            }else {
                tmp.next = cur;
                tmp = tmp.next;
            }
            cur = cur.next;
        }
        //最后一个不重复节点的next域置空(防止最后一个节点也是重复的)
        tmp.next = null;
        return newHead.next;
    }

    //链表分割
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null;//小于X的起始
        ListNode be = null;//小于X的终止
        ListNode as = null;//大于X的起始
        ListNode ae = null;//大于X的终止
        ListNode cur = pHead;//使用cur遍历源链表
        while (cur != null){
            if (cur.val >= x){
                if (bs == null){
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if (as == null){
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //预防第一个段为空
        if (as == null){
            return bs;
        }
        ae.next = bs;
        //将最后一个节点的next置为null，防止指向成环。
        if (bs != null){
            be.next = null;
        }
        return as;
    }

    //返回链表的中间节点
    public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //链表的回文结构判断
    //解法2
    public boolean chkPalindrome(ListNode A) {
        if (A == null || A.next == null){
            return true;
        }
        //1、找到中间节点，调用写过的代码
        ListNode midNode = middleNode(A);
        //2、从中间节点往后逆置
        ListNode cur = midNode.next;
        ListNode prev = midNode;
        while (cur != null){
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        //此时，前半段的末尾指向mid，后半段的末尾也指向mid
        //与反转链表不同的是，反转完成后mid的指向不需要指向null
        //3、从两端开始判断回文
        //奇数情况下：
        while (A != prev){
            int val1 = A.val;
            int val2 = prev.val;
            if (val1 != val2){
                return false;
            }
            //考虑偶数情况
            if (A.next == prev){
                return true;
            }
            A = A.next;
            prev = prev.next;

        }
        return true;
    }
    //解法1
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null){
            list.add(cur.val);
            cur = cur.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while (left < right){
            if (list.get(left) != list.get(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    //两个升序链表合并为一个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (list1 != null && list2 != null){
            int val1 = list1.val;
            int val2 = list2.val;
            if (val1 > val2){
                cur.next = list2;
                list2 = list2.next;
            }else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if (list1 == null){
            cur.next = list2;
        }
        if (list2 == null){
            cur.next = list1;
        }
        return head.next;
    }

    //链表当中倒数第k个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (k <= 0){
            return null;
        }
        int size = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            size++;
        }
        if (k > size){
            return null;
        }
        int index = size - k;
        ListNode tmp = head;
        for (int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        return tmp;
    }
    //思路2：快慢指针
    public ListNode getKthFromEnd2(ListNode head, int k) {
        if (k <= 0){
            return null;
        }
        int size = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            size++;
        }
        if (k > size){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //先让fast走k-1步
        while (k - 1 != 0){
            fast = fast.next;
            k--;
        }
        //再让fast和slow同时走
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //链表翻转
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
/*        ListNode prev = head;
        ListNode cur = prev.next;
        while (cur != null){
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        head.next = null;
        return prev;*/
        //头插法
        ListNode cur = head.next;
        head.next = null;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}
